package com.example.question.tree.tree3;

import com.example.question.tree.tree1.TreeNode;

public class Code16_654 {

    public static void main(String[] args) {
//        constructMaximumBinaryTree(new int[]{3, 2, 1, 6, 0, 5});
        Code16_654 code = new Code16_654();
        TreeNode treeNode = code.constructMaximumBinaryTree(new int[]{3, 2, 1, 6, 0, 5});
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        this.nums = nums;
        return buildTree(0, nums.length - 1);
    }

    private int[] nums;

    private TreeNode buildTree(int left, int right) {
        if (left > right) {
            return null;
        }
        int maxValIndex = findMaxValIndex(left, right);
        TreeNode treeNode = new TreeNode(nums[maxValIndex]);
        treeNode.left = buildTree(left, maxValIndex - 1);
        treeNode.right = buildTree(maxValIndex + 1, right);
        return treeNode;
    }

    private int findMaxValIndex(int left, int right) {
        int maxVal = nums[left];
        int maxValIndex = left;
        for (int i = left; i < right + 1; i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                maxValIndex = i;
            }
        }
        return maxValIndex;
    }
}
